package com.xie.leetcode.string;

//20. 有效的括号
//        给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
//        有效字符串需满足：
//
//        左括号必须用相同类型的右括号闭合。
//        左括号必须以正确的顺序闭合。
//
//
//        示例 1：
//
//        输入：s = "()"
//        输出：true
//        示例 2：
//
//        输入：s = "()[]{}"
//        输出：true
//        示例 3：
//
//        输入：s = "(]"
//        输出：false
//        示例 4：
//
//        输入：s = "([)]"
//        输出：false
//        示例 5：
//
//        输入：s = "{[]}"
//        输出：true
//
//
//        提示：
//
//        1 <= s.length <= 104
//        s 仅由括号 '()[]{}' 组成

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author xiezhendong
 * @date 2021/11/1
 */
public class IsValid {

    public static void main(String[] args) {
        IsValid isValid = new IsValid();
        System.out.println(isValid.isValid("()"));
        System.out.println(isValid.isValid("()[]{}"));
        System.out.println(isValid.isValid("(]"));
        System.out.println(isValid.isValid("([)]"));
        System.out.println(isValid.isValid("{[]}"));
    }

    public boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;
        }
        Deque<String> deque = new LinkedList<>();
        for (char c : s.toCharArray()) {
            String str = String.valueOf(c);
            if ("(".equals(str)) {
                deque.push(")");
            } else if ("{".equals(str)) {
                deque.push("}");
            } else if ("[".equals(str)) {
                deque.push("]");
            } else if (deque.isEmpty() || !deque.peek().equals(str)) {
                return false;
            } else {
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
}
